package com.xj.algorithm.leetcode;

import java.util.ArrayDeque;
import java.util.Queue;

/**
 * 左叶子之和
 */
public class L404_左叶子累加和 {

    /**
     * 计算给定二叉树的所有左叶子之和。
     * <p>
     * 示例：
     * <p>
     * 3
     * / \
     * 9  20
     * /  \
     * 15   7
     * <p>
     * 在这个二叉树中，有两个左叶子，分别是 9 和 15，所以返回 24
     */
    public static void main(String[] args) {
        TreeNode root = new TreeNode(3);
        root.left = new TreeNode(9);
        root.right = new TreeNode(20);
        root.right.left = new TreeNode(15);
        root.right.right = new TreeNode(7);
        System.out.println(sumOfLeftLeavesOffice(root));

        TreeNode root2 = new TreeNode(1);
        root2.left = new TreeNode(2);
        root2.right = new TreeNode(3);
        root2.left.left = new TreeNode(4);
        root2.right.right = new TreeNode(5);
        System.out.println(sumOfLeftLeavesOffice(root2));
    }

    //自己的解法：层次遍历，遇到左孩子，再判断左孩子是否是叶子
    public static int sumOfLeftLeaves(TreeNode root) {
        if(root==null){
            return 0;
        }

        Queue<TreeNode> queue = new ArrayDeque<>();
        queue.add(root);
        int sum=0;
        while (!queue.isEmpty()) {
            TreeNode node=queue.poll();

            if (node.left != null) {
                if (node.left.left != null || node.left.right != null) {
                    queue.add(node.left);
                }else{
                  sum+=node.left.val;
                }
            }

            if (node.right != null) {
                if (node.right.left != null || node.right.right != null) {
                    queue.add(node.right);
                }
            }
        }
        return sum;
    }

    //官方解法：递归找左叶子
    public static int sumOfLeftLeavesOffice(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int sum = 0;
        if (isLeftLeave(root.left)) {
            sum += root.left.val;
        } else {
            sum += sumOfLeftLeavesOffice(root.left);
        }
        sum += sumOfLeftLeavesOffice(root.right);
        return sum;
    }

    public static boolean isLeftLeave(TreeNode treeNode) {
        return treeNode != null && (treeNode.left == null && treeNode.right == null);
    }
}
